Выпуклая оптимизация: За пределами базовой выпуклости: Сохранение через точечный супремум

Хотя базовая выпуклость охватывает суммы и масштабирование, сохранение выпуклости через точечный супремум является фундаментальной операцией для построения нетривиальных выпуклых функций и установления двойственности. Она утверждает, что даже если у нас есть несчетное бесконечное семейство выпуклых функций, их «верхняя оболочка» остается выпуклой. Этот мост позволяет анализировать сложные выпуклые формы с помощью простых линейных компонентов.

1. Техническое определение

Для семейства функций $\{f(\cdot, y) \mid y \in \mathcal{A}\}$ точечный супремум определяется как:

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y)$$

Область определения этой функции — это множество точек, где все функции в семействе определены и супремум конечен:

$$\text{dom } g = \{x \mid (x, y) \in \text{dom } f \text{ для всех } y \in \mathcal{A}, \sup_{y \in \mathcal{A}} f(x, y) < \infty\}$$

Перспектива эпиграфа

Геометрически эпиграф функции супремума — это пересечение отдельных эпиграфов:

$$\text{epi } g = \bigcap_{y \in \mathcal{A}} \text{epi } f(\cdot, y)$$

Поскольку каждый отдельный эпиграф является выпуклым множеством (из-за выпуклости $f(x, y)$ по $x$), а пересечение любого числа выпуклых множеств само по себе выпукло, выпуклость $g(x)$ гарантирована.

2. Значимые примеры

Функция поддержки: $S_C(y) = \sup \{ y^T x \mid x \in C \}$. Эта функция всегда выпукла, независимо от того, выпукло ли множество $C$, потому что она является супремумом линейных (аффинных) функций от $y$.
Расстояние до самой удалённой точки: $f(x) = \sup_{y \in C} \|x - y\|$. Даже для множества $C$ неправильной формы $f(x)$ выпукла по $x$, потому что норма — это выпуклая функция от $x$.
Максимальное собственное значение: Для симметричной матрицы $X$, $f(X) = \lambda_{\max}(X)$ выпукла. Это следует из квадратичной формы Рэлея: $\lambda_{\max}(X) = \sup\{y^T X y \mid \|y\|_2 = 1\}$. Это супремум линейных функций от $X$.

Теорема: Представление через аффинные функции

Теорема

Почти каждая выпуклая функция может быть выражена как точечный супремум семейства аффинных функций (глобальных нижних оценок).

Интуиция

В каждой точке $x_0$ выпуклая функция $f$ имеет опорную гиперплоскость (аффинную функцию $h(x) = f(x_0) + g^T(x-x_0)$). Взяв супремум всех таких опорных гиперплоскостей, мы точно восстанавливаем функцию $f$.

🎯 Основной принцип

Точечный супремум сохраняет выпуклость, а точечный инфимум сохраняет вогнутость. Это секрет выпуклости норм, спектральных функций и двойственных задач.

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y) \implies g \text{ выпукла, если } f(\cdot, y) \text{ выпукла } \forall y$$

ВОПРОС 1

Если $f_1(x), f_2(x), \dots, f_n(x)$ — выпуклые функции, что можно сказать о $g(x) = \max\{f_1(x), \dots, f_n(x)\}$?

$g(x)$ всегда выпукла.

$g(x)$ выпукла только если все $f_i$ линейны.

$g(x)$ вогнута.

$g(x)$ только квази-выпукла.

ВОПРОС 2

Функция поддержки $S_C(y) = \sup_{x \in C} y^T x$ выпукла по $y$, даже если $C$ — невыпуклое множество. Почему?

Потому что $y^T x$ линейна (и следовательно, выпукла) по $y$ при любом фиксированном $x$.

Потому что множество $C$ автоматически рассматривается как его выпуклая оболочка.

Потому что скалярное произведение всегда положительная функция.

Функции поддержки выпуклы только если $C$ ограничено.

ВОПРОС 3

Какова связь между эпиграфом $g(x) = \sup f_i(x)$ и отдельными эпиграфами $\text{epi } f_i$?

$\text{epi } g = \bigcap \text{epi } f_i$

$\text{epi } g = \bigcup \text{epi } f_i$

$\text{epi } g = \text{conv}(\bigcup \text{epi } f_i)$

Нет прямой связи.

ВОПРОС 4

Спектральная норма матрицы $\|X\|_2 = \sigma_{\max}(X)$ выпукла, потому что...

Это супремум выпуклых функций $\|Xv\|_2$ по единичным векторам $v$.

Сумма сингулярных значений всегда выпукла.

Все нормы — линейные функции.

Матричные функции всегда выпуклы на положительно полуопределённом конусе.

ВОПРОС 5

Что получится, если взять точечный инфимум семейства вогнутых функций?

Вогнутая функция.

Выпуклая функция.

Линейная функция.

Зависит от области определения.

Вызов: Дуальность и сопряжённые функции

MATH008 Расширенный анализ

В выпуклом анализе сопряжённая функция $f^*$ определяется через точечный супремум аффинных функций: $f^*(y) = \sup_x (y^T x - f(x))$. Это преобразование жизненно важно для двойственных задач оптимизации.

В1

[Краткий ответ] Условие второго порядка для выпуклости. Докажите, что дважды дифференцируемая функция $f$ выпукла тогда и только тогда, когда её область определения выпукла и $\nabla^2 f(x) \succeq 0$ для всех $x \in \mathbf{dom} f.

Решение: Ограничив функцию $f$ произвольной прямой $g(t) = f(x + tv)$, выпуклость $f$ эквивалентна $g''(t) \geq 0$ для всех $v$ и всех $t$, при которых $x+tv \in \text{dom } f$. Поскольку $g'(t) = \nabla f(x + tv)^T v$ и $g''(t) = v^T \nabla^2 f(x + tv) v$, условие $g''(t) \geq 0$ для всех $v$ эквивалентно тому, что матрица Гессе положительно полуопределена: $\nabla^2 f(x) \succeq 0$.

В2

[Краткий ответ] Градиент и гессиан сопряжённой функции. Пусть $\bar{y}$ и $\bar{x}$ связаны соотношением $\bar{y} = \nabla f(\bar{x})$, и $\nabla^2 f(\bar{x}) \succ 0$. (a) Покажите, что $\nabla f^*(\bar{y}) = \bar{x}$. (b) Покажите, что $\nabla^2 f^*(\bar{y}) = \nabla^2 f(\bar{x})^{-1}$. (Требуется: 250 слов)

Ответ преподавателя: Чтобы решить часть (a), вспомним определение сопряжённой функции $f^*(y) = \sup_x (y^T x - f(x))$. При фиксированном $y = \bar{y}$, если $f$ дифференцируема и выпукла, супремум достигается в точке, где градиент цели $h(x) = \bar{y}^T x - f(x)$ обращается в ноль. Установив $\nabla_x (\bar{y}^T x - f(x)) = 0$, получаем $\bar{y} = \nabla f(x)$. Поскольку в условии сказано $\bar{y} = \nabla f(\bar{x})$, следует, что $\bar{x}$ — максимизатор. По свойству сопряжённой функции в точке оптимума имеем $f^*(\bar{y}) = \bar{y}^T \bar{x} - f(\bar{x})$. Дифференцируя обе части по $\bar{y}$ и применяя теорему об обёртке (или тот факт, что $\bar{x}$ — оптимизатор), получаем $\nabla f^*(\bar{y}) = \bar{x}$. Это подтверждает, что градиент сопряжённой функции действует как обратное отображение градиента исходной функции.

For part (b), we differentiate the relationship $\nabla f^*(\nabla f(x)) = x$ with respect to $x$ using the chain rule. This gives $\nabla^2 f^*(\nabla f(x)) \cdot \nabla^2 f(x) = I$, where $I$ is the identity matrix. Substituting $\bar{y} = \nabla f(\bar{x})$, we get $\nabla^2 f^*(\bar{y}) \cdot \nabla^2 f(\bar{x}) = I$. Since we are given $\nabla^2 f(\bar{x}) \succ 0$, the Hessian is invertible. Thus, $\nabla^2 f^*(\bar{y}) = [\nabla^2 f(\bar{x})]^{-1}$. This elegant result shows that the local curvature of the conjugate function is the reciprocal (or inverse matrix) of the curvature of the original function at corresponding points. This relationship is central to the analysis of Newton-type methods in dual space and the understanding of Legendre transforms in physics and optimization.